package main

func mySqrt(x int) int {
	if x == 0 {
		return 0
	}
	if x == 1 {
		return 1
	}
	i := 1
	j := x - 1
	for i <= j {
		mid := i + (j-i)/2
		pow := mid * mid
		if pow < x {
			i = mid + 1
		} else if pow > x {
			j = mid - 1
		} else {
			return mid
		}
	}
	return j
}

func main() {
	println(mySqrt(5))
	println(mySqrt(6))
	println(mySqrt(9))
	println(mySqrt(11))
}
